use std::rc::Rc;
use crate::expr::{Assign, Binary, Call, ExprTrait, Expression, Grouping, Literal, Logical, Triple, Unary, Variable, Get, Set, This, Super};
use crate::scanner::{LiteralValue, Token, TokenType};
use crate::stmt::{Stmt, StmtBlock, StmtClass, StmtExpr, StmtFunction, StmtIf, StmtPrint, StmtReturn, StmtVar, StmtWhile};

pub struct Parser {
    tokens: Vec<Token>,
    current: usize
}

type ExprParseResult = Result<Expression, String>;
type StmtParseResult = Result<Stmt, String>;

impl Parser {
    pub fn new(tokens: Vec<Token>) -> Self {
        Self {tokens, current: 0}
    }

    /*
    program ::= declaration* EOF;
    declaration ::= classDecl
                    | funDecl
                    | varDeclaration
                    | statement;
    classDecl = "class" IDENTIFIER ("<" IDENTIFIER)? "{" function* "}"
    funDecl ::= "fun" function;
    function = IDENTIFIER "(" parameters? ")" block ;
    varDeclaration ::= "var" IDENTIFIER ( "=" expression )? ";";
    statement ::= exprStmt
                  | forStmt
                  | returnStmt
                  | breakStmt
                  | continueStmt
                  | ifStmt
                  | printStmt
                  | whileStmt
                  | block;
    ifStmt = "if" "(" expression ")" statement ("else" statement )? ;
    exprStmt ::= expression ";";
    forStmt ::= "for" "("(varDecl | exprStmt ";") expression? ; expression?; ")" statement ;
    returnStmt ::= "return" expression? ";";
    printStmt ::= "print" expression ";";
    whileStmt ::= "while" "(" expression ")" statement;
    block ::= "{" declaration* "}";
    expression ::= assignment;
    assignment ::= ( call ".")? IDENTIFIER "=" assignment | logic_or;
    logic_or ::= logic_and ( "or" logic_and)* ;
    logic_and ::= triple ( "and" triple)* ;
    triple ::= equality? triple: triple
    equality ::= comparison ( ( "!=" | "==" ) comparison )* ;
    comparison ::= term ( ( ">" | ">=" | "<" | "<=" ) term )* ;
    term ::= factor ( ( "-" | "+" ) factor )* ;
    factor ::= unary ( ( "/" | "*" ) unary )* ;
    unary ::= ( "!" | "-" ) unary | call ;
    call ::= primary ( "(" arguments? ")" | "." IDENTIFIER )*
    arguments ::= expression ("," expression )*
    parameters ::= IDENTIFIER ( "," IDENTIFIER )* ;
    primary ::= NUMBER
                | STRING
                | "true"
                | "false"
                | "nil"
                | "(" expression ")"
                | IDENTIFIER
                | "super" "." IDENTIFIER;
     */

    pub fn parse(&mut self) -> Result<Vec<Stmt>, String> {
        let mut ret = Vec::new();
        while !self.is_at_end() {
            ret.push(self.declaration().map_err(|e| e)?);
        }

        Ok(ret)
    }

    fn declaration(&mut self) -> StmtParseResult {
        if self.match_token_type(TokenType::Class) {
            self.class_declaration()
        } else if self.match_token_type(TokenType::Var) {
            self.var_declaration()
        } else if self.match_token_type(TokenType::Fun) {
            self.function("function")
        } else {
            self.statement()
        }
    }

    fn class_declaration(&mut self) -> StmtParseResult {
        let name = self.consume(TokenType::Identifier, "Expect class name".to_string())?;
        let mut superclass_op: Option<Variable> = None;
        if self.match_token_type(TokenType::Less) {
            let superclass = self.consume(TokenType::Identifier, "Expect super class".to_string())?;
            superclass_op = Some(Variable{ token: superclass });
        }
        self.consume(TokenType::LeftBrace, "Expect '{' after class name".to_string())?;
        let mut methods = Vec::new();
        while !self.check(TokenType::RightBrace) && !self.is_at_end() {
            match self.function("method")? {
                Stmt::Function(f) => {
                    methods.push(f)
                },
                _ => return Err("impossible".to_string())
            }
        }

        self.consume(TokenType::RightBrace, "Expect '}' after class body".to_string())?;
        Ok(Stmt::Class(StmtClass{ name, methods, superclass: superclass_op }))
    }

    fn function(&mut self, kind: &str) -> StmtParseResult {
        let name = self.consume(TokenType::Identifier, format!("Expected {} name.", kind))?;
        self.consume(TokenType::LeftParent, format!("Expect '(' after {} name.", kind))?;
        let mut params: Vec<Token> = Vec::new();
        if !self.check(TokenType::RightParent) {
            loop {
                if params.len() >= 255 {
                    return Err("Can't have more than 255 parameters.".to_string());
                }

                params.push(self.consume(TokenType::Identifier, "Expect identifier name".to_string())?);
                if !self.match_token_type(TokenType::Comma) {
                    break;
                }
            }
        }

        self.consume(TokenType::RightParent, format!("Expect '(' after {} name.", kind))?;

        self.consume(TokenType::LeftBrace, "Expect '{' for function body".to_string())?;

        let body = self.block()?;

        // println!("parse function:{:?}: {}",body,  &name.lexeme);
        Ok(Stmt::Function(StmtFunction{ name, params, body }))
    }

    fn var_declaration(&mut self) -> StmtParseResult {
        let name = self.consume(TokenType::Identifier, "Expect variable name.".to_string()).map_err(|e| e)?;
        let ret = if self.match_token_type(TokenType::Equal) {
            Ok(Stmt::Var(StmtVar {name, initializer: self.expression().map_err(|e| e)?}))
        } else {
            Ok(Stmt::Var(StmtVar {name, initializer: Expression::nil()}))
        };

        self.consume(TokenType::Semicolon, "Expect ';' after variable declaration.".to_string())?;

        ret
    }

    fn statement(&mut self) -> StmtParseResult {
        if self.match_token_type(TokenType::Print) {
            self.print_statement()
        } else if self.match_token_type(TokenType::LeftBrace) {
            let mut stmts = self.block()?;
            stmts.reverse();
            let mut stmts_ag = Vec::new();
            while !stmts.is_empty() {
                stmts_ag.push(stmts.pop().unwrap())
            }

            Ok(Stmt::Block(StmtBlock { stmts: stmts_ag}))
        } else if self.match_token_type(TokenType::If) {
            self.consume(TokenType::LeftParent, "Expect '(' after 'if'.".to_string())?;
            let condition = self.triple()?;
            self.consume(TokenType::RightParent, "Expect ')' after 'if'.".to_string())?;

            let then_stmt = self.statement()?;
            if self.match_token_type(TokenType::Else) {
                let else_stmt = self.statement()?;
                Ok(Stmt::If(StmtIf { condition, then_stmt: Rc::new(then_stmt), else_stmt: Some(Rc::new(else_stmt)) }))
            } else {
                Ok(Stmt::If(StmtIf { condition, then_stmt: Rc::new(then_stmt), else_stmt: None }))
            }
        } else if self.match_token_type(TokenType::While) {
            self.consume(TokenType::LeftParent, "Expect '(' after 'while'.".to_string())?;
            let condition = self.triple()?;
            self.consume(TokenType::RightParent, "Expect ')' after 'while'.".to_string())?;
            let body = self.statement()?;
            Ok(Stmt::While(StmtWhile { condition, body: Rc::new(body) }))
        } else if self.match_token_type(TokenType::For) {
            self.consume(TokenType::LeftParent, "Expect '(' after 'for'".to_string())?;
            let init_op: Option<Stmt> = if self.match_token_type(TokenType::Semicolon) {
                None
            } else if self.match_token_type(TokenType::Var) {
                Some(self.var_declaration()?)
            } else {
                Some(self.expression_statement()?)
            };

            let condition: Expression = if self.match_token_type(TokenType::Semicolon) {
                Expression::new_bool(true)
            } else {
                self.expression()?
            };

            self.consume(TokenType::Semicolon, "Expect ':' after loop condition".to_string())?;

            let increment_op: Option<Expression> = if !self.match_token_type(TokenType::RightParent) {
                Some(self.expression()?)
            } else {
                None
            };
            self.consume(TokenType::RightParent, "Expect ')' after for clauses.".to_string())?;

            let body = self.statement()?;

            let body_block: Stmt = if increment_op.is_some() {
                let expr_stmt = Stmt::Expression(StmtExpr {expr: increment_op.unwrap()});
                Stmt::Block(StmtBlock {stmts: vec![body, expr_stmt]})
            } else {
                body
            };

            let mut block_stmts = Vec::new();
            if init_op.is_some() {
                block_stmts.push(init_op.unwrap());
            }

            let while_expr = Stmt::While(StmtWhile { condition, body: Rc::new(body_block) });
            block_stmts.push(while_expr);
            Ok(Stmt::Block(StmtBlock { stmts: block_stmts}))
        } else if self.match_token_type(TokenType::Break) {
            self.consume(TokenType::Semicolon, "Expect ';' after break".to_string())?;
            Ok(Stmt::Break)
        } else if self.match_token_type(TokenType::Continue) {
            self.consume(TokenType::Semicolon, "Expect ';' after continue".to_string())?;
            Ok(Stmt::Continue)
        } else if self.match_token_type(TokenType::Return) {
            self.return_statement()
        } else {
            self.expression_statement()
        }
    }

    fn block(&mut self) -> Result<Vec<Stmt>, String> {
        let mut ret = Vec::new();
        while !self.check(TokenType::RightBrace) && !self.is_at_end() {
            ret.push(self.declaration()?);
        }

        self.consume(TokenType::RightBrace, "Expect '}' after block.".to_string())?;

        Ok(ret)
    }

    fn print_statement(&mut self) -> StmtParseResult {
        let value = self.expression()?;
        self.consume(TokenType::Semicolon, "Expect ';' after value.".to_string())?;
        Ok(Stmt::Print(StmtPrint{ expr: value}))
    }

    fn expression_statement(&mut self) -> StmtParseResult {
        let expr = self.expression()?;
        self.consume(TokenType::Semicolon, "Expect ';' after value.".to_string())?;
        Ok(Stmt::Expression(StmtExpr {expr}))
    }

    fn return_statement(&mut self) -> StmtParseResult {
        let keyword = self.previous().clone();
        let value: Option<Expression> = if self.check(TokenType::Comma) {
            None
        } else {
            Some(self.expression()?)
        };
        self.consume(TokenType::Semicolon, "Expect ';' after return value.".to_string())?;
        Ok(Stmt::Return(StmtReturn { keyword, value }))
    }

    pub fn expression(&mut self) -> ExprParseResult {
        self.assignment()
    }

    pub fn assignment(&mut self) -> ExprParseResult {
        let expr = self.or()?;
        if self.match_token_type(TokenType::Equal) {
            let equals = self.previous().clone();
            let value = self.assignment()?;

            match expr {
                Expression::Variable(name) => Ok(Expression::Assign(
                    Assign{
                        name: name.token.clone(),
                        value: Rc::new(value)
                    })),
                Expression::Get(get) => Ok(Expression::Set(Set {
                    object: get.object.clone(),
                    name: get.name.clone(),
                    value: Rc::new(value)
                })),
                _ => Err(format!("{:?}: invalid assignment target.", equals))
            }

        } else {
            Ok(expr)
        }
    }

    pub fn or(&mut self) -> ExprParseResult {
        let mut expr = self.and()?;
        while self.match_token_type(TokenType::Or) {
            let operator = self.previous().clone();
            let and = self.and()?;
            expr = Expression::Logical(Logical{ left: Rc::new(expr), operator, right: Rc::new(and) })
        }
        Ok(expr)
    }

    pub fn and(&mut self) -> ExprParseResult {
        let mut expr = self.triple()?;
        while self.match_token_type(TokenType::And) {
            let operator = self.previous().clone();
            let triple = self.triple()?;
            expr = Expression::Logical(Logical{ left: Rc::new(expr), operator, right: Rc::new(triple)})
        }

        Ok(expr)
    }

    pub fn triple(&mut self) -> ExprParseResult {
        let mut expr = self.equality()?;

        if self.match_token_type(TokenType::QuestionMark) {
            let true_expr = self.triple()?;
            self.consume(TokenType::Colon, "invalid triple token".to_string()).map_err(|e| e)?;
            let false_expr = self.triple()?;
            expr = Expression::Triple(Triple { judge_expr: Rc::new(expr), true_expr: Rc::new(true_expr), false_expr: Rc::new(false_expr) });
        }

        Ok(expr)
    }

    fn equality(&mut self) -> ExprParseResult {
        let mut expr = self.comparison()?;
        let types = vec![TokenType::Bang, TokenType::BangEqual];
        while self.match_token_types(&types) {
            let operator = self.previous().clone();
            let right = self.comparison()?;
            expr = Expression::Binary(Binary {left: Rc::new(expr), operator, right: Rc::new(right) });
        }

        Ok(expr)
    }

    fn comparison(&mut self) -> ExprParseResult {
        let mut expr = self.term()?;

        let types = vec![
            TokenType::Greater, TokenType::GreaterEqual,
            TokenType::Less, TokenType::LessEqual
        ];

        while self.match_token_types(&types) {
            let operator = self.previous().clone();
            let right = self.term()?;
            expr = Expression::Binary(Binary { left: Rc::new(expr), operator, right: Rc::new(right) });
        }

        Ok(expr)
    }

    fn term(&mut self) -> ExprParseResult {
        let mut expr = self.factor()?;

        let types = vec![TokenType::Minus, TokenType::Plus];
        while self.match_token_types(&types) {
            let operator = self.previous().clone();
            let right = self.factor()?;
            expr = Expression::Binary(Binary { left: Rc::new(expr), operator, right: Rc::new(right)});
        }

        Ok(expr)
    }

    fn factor(&mut self) -> ExprParseResult {
        let mut expr = self.unary()?;

        let types = vec![TokenType::Slash, TokenType::Star];
        while self.match_token_types(&types) {
            let operator = self.previous().clone();
            let right = self.unary()?;
            expr = Expression::Binary(Binary { left: Rc::new(expr), operator, right: Rc::new(right)});
        }

        Ok(expr)
    }

    fn unary(&mut self) -> ExprParseResult {
        let types = vec![TokenType::Bang, TokenType::Minus];
        if self.match_token_types(&types) {
            let operator = self.previous().clone();
            let right = self.unary()?;
            Ok(Expression::Unary(Unary {operator, right: Rc::new(right)}))
        } else {
            Ok(self.call()?)
        }
    }

    fn call(&mut self) -> ExprParseResult {
        let mut expr = self.primary()?;
        loop {
            if self.match_token_type(TokenType::LeftParent) {
                expr = self.finish_call(expr)?;
            } else if self.match_token_type(TokenType::Dot) {
                let name = self.consume(TokenType::Identifier, "Expect property name after '.'".to_string())?;
                expr = Expression::Get(Get { name, object: Rc::new(expr) });
            } else {
                break;
            }
        }

        Ok(expr)
    }

    fn primary(&mut self) -> ExprParseResult {
        if self.match_token_type(TokenType::Number) {
            Ok(Expression::Literal(Literal { value: self.previous().literal.clone() }))
        } else if self.match_token_type(TokenType::String) {
            Ok(Expression::Literal(Literal { value: self.previous().literal.clone() }))
        } else if self.match_token_type(TokenType::False) {
            Ok(Expression::new_bool(false))
        } else if self.match_token_type(TokenType::True) {
            Ok(Expression::new_bool(true))
        } else if self.match_token_type(TokenType::Nil) {
            Ok(Expression::nil())
        } else if self.match_token_type(TokenType::Identifier) {
            Ok(Expression::Variable(Variable { token: self.previous().clone()}))
        } else if self.match_token_type(TokenType::This) {
            Ok(Expression::This(This { keyword: self.previous().clone() }))
        } else if self.match_token_type(TokenType::Super) {
            let keyword = self.previous().clone();
            self.consume(TokenType::Dot, "missing '.' after super".to_string())?;
            let method = self.consume(TokenType::Identifier, "Expect superclass method name.".to_string())?;
            Ok(Expression::Super(Super { keyword, method }))
        }
        else {
            if self.match_token_type(TokenType::LeftParent) {
                let expr = self.expression()?;
                self.consume(TokenType::RightParent, "Expect ')' after expression.".to_string()).map_err(|e| e)?;
                Ok(Expression::Grouping(Grouping{ expr: Rc::new(expr)}))
            } else {
                Err("nothing primary match".to_string())
            }
        }
    }

    fn finish_call(&mut self, callee: Expression) -> ExprParseResult {
        let mut arguments: Vec<Expression> = Vec::new();

        if !self.check(TokenType::RightParent) {
            loop {
                arguments.push(self.expression()?);
                if arguments.len() >= 255 {
                    return Err("Can't have more than 255 arguments.".to_string());
                }
                if !self.match_token_type(TokenType::Comma) {
                    break;
                }
            }
        }

        let parent = self.consume(TokenType::RightParent, "Expect ')' after arguments.".to_string())?;
        Ok(Expression::Call(Call {callee: Rc::new(callee), parent, arguments}))
    }

    fn consume(&mut self, token_type: TokenType, msg: String) -> Result<Token, String> {
        if self.check(token_type) {
            Ok(self.advance().clone())
        } else {
            Err(msg)
        }
    }

    fn match_token_types(&mut self, types: &[TokenType]) -> bool {
        for token_type in types.iter() {
            if self.check(token_type.clone()) {
                self.advance();
                return true;
            }
        }

        false
    }

    fn match_token_type(&mut self, token_type: TokenType) -> bool {
        if self.check(token_type) {
            self.advance();
            true
        } else {
            false
        }
    }

    fn advance(&mut self) -> &Token {
        if !self.is_at_end() { self.current += 1; }

        self.previous()
    }


    fn check(&self, token_type: TokenType) -> bool {
        self.peek().t_type == token_type
    }

    fn previous(&self) -> &Token {
        self.tokens.get(self.current - 1).unwrap()
    }

    fn peek(&self) -> &Token {
        self.tokens.get(self.current).unwrap()
    }

    fn is_at_end(&self) -> bool {
        self.peek().t_type == TokenType::Eof
    }
}

#[cfg(test)]
mod test {
    use crate::parser::Parser;
    use crate::scanner::Scanner;

    #[test]
    fn parse_test() {
        let s = "3 * (2 + 1)";

        let mut scanner = Scanner::new(s);
        let tokens = scanner.scan_tokens().unwrap();

        let mut parser = Parser::new(tokens);

        println!("{:?}", parser.expression());
    }

    #[test]
    fn parse_triple() {
        let s = "2 > 3? 1:2";

        let mut scanner = Scanner::new(s);
        let tokens = scanner.scan_tokens().unwrap();

        let mut parser = Parser::new(tokens);

        println!("{:?}", parser.expression());
    }

    #[test]
    fn parse_stmt() {
        let ss = vec![
            "print \"123\";",
            "1+2;"
        ];
        for s in ss.iter() {
            let mut scanner = Scanner::new(s);
            let tokens = scanner.scan_tokens().unwrap();

            let mut parser = Parser::new(tokens);

            println!("{:?}", parser.parse());
        }
    }

    #[test]
    fn parse_block() {
        let s = "var a = 1;
{
var b = 1 or 2 and 3;
print a;
}";
        let mut scanner = Scanner::new(s);
        let tokens = scanner.scan_tokens().unwrap();
        println!("tokens: {:?}", tokens);

        let mut parser = Parser::new(tokens);

        println!("{:?}", parser.parse());
    }

    #[test]
    fn parse_while() {
        let s = "var i = 1;
        var sum = 0;
        while (i < 10) {
            sum = sum + 1;
        }
        print sum
        ";

        let mut scanner = Scanner::new(s);
        let tokens = scanner.scan_tokens().unwrap();
        println!("tokens: {:?}", tokens);

        let mut parser = Parser::new(tokens);

        println!("{:?}", parser.parse());
    }

    #[test]
    fn parse_class() {
        let s= "class Foo {\
            hi(msg) {
                print msg;
            }
        }";

        parse(s);
    }

    #[test]
    fn parse_instance() {
        let s = "class Foo {\
        }\
        \
        var ins = Foo();
        print ins.a;
        ";
        parse(s);
    }

    fn parse(s: &str) {
        let mut scanner = Scanner::new(s);
        let tokens = scanner.scan_tokens().unwrap();
        println!("tokens: {:?}", tokens);

        let mut parser = Parser::new(tokens);

        println!("{:?}", parser.parse());
    }
}